package List;
class ListNodeD {
    public int data;
    public ListNodeD prev;
    public ListNodeD next;

    public ListNodeD(int data) {
        this.data = data;
    }
}
public class MyRealinkedList {
    public ListNodeD head;
    public ListNodeD last;
    public MyRealinkedList(){

    }
    public void addFirst(int data) {
        ListNodeD node=new ListNodeD(data);
        if (this.head==null){
            this.head=node;
        }
        else {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }
    public void addLast(int data) {
        ListNodeD node=new ListNodeD(data);
        if (this.head==null){
            this.head=node;
            this.last=node;
        }
        else {
            this.last.next=node;
            node.prev=this.last;
            this.last=node;
        }
    }
    public ListNodeD findIndex(int index) {
        ListNodeD node=this.head;
        while (index!=0){
            index--;
            node=node.next;
        }
        return node;
    }
    public void addIndex(int index,int data) {
        if(index<0||index>size()){
            System.out.println("index位置不合法");
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        ListNodeD cur=findIndex(index);
        ListNodeD node=new ListNodeD(data);
        node.next=cur;
        cur.prev.next=node;
        node.prev=cur.prev;
        cur.prev=node;
    }
    public int size() {
        int count = 0;
        if(this.head == null) return count;
        ListNodeD cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    public boolean contains(int key) {
        if(this.head==null){
            return false;
        }
        ListNodeD cur=this.head;
        while (cur!=null){
            if(cur.data==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    public void display() {
        if(this.head==null){
            return;
        }
        ListNodeD cur=this.head;
        while (cur!=null){
            System.out.print(cur.data+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    public void remove(int key) {
        ListNodeD cur=this.head;
        while (cur!=null){
            if (cur.data==key) {
                if (cur==this.head){
                    this.head = this.head.next;
                    if(this.head == null) {
                        this.last = null;
                    }else {
                        this.head.prev = null;
                    }
                }
                else {
                    cur.prev.next=cur.next;
                    if(cur.next==null){
                        this.last=cur.prev;
                    }
                    else {
                        cur.next.prev=cur.prev;
                    }
                }
                return;
            }
            else {
                cur=cur.next;
            }
        }
    }
    public void removeAllKey(int key) {
        ListNodeD cur=this.head;
        while (cur!=null){
            if (cur.data==key) {
                if (cur==this.head){
                    this.head = this.head.next;
                    if(this.head == null) {
                        this.last = null;
                    }else {
                        this.head.prev = null;
                    }
                }
                else {
                    cur.prev.next=cur.next;
                    if(cur.next==null){
                        this.last=cur.prev;
                    }
                    else {
                        cur.next.prev=cur.prev;
                    }
                }
                cur=cur.next;
            }
            else {
                cur=cur.next;
            }
        }
    }
    public void clear() {
        ListNodeD cur=this.head;
        while (cur!=null){
            ListNodeD curNext=cur.next;
            cur.prev=null;
            cur.next=null;
            cur=curNext;
        }
        this.last=null;
        this.head=null;
    }
}
